package LeetCode_110;

/**
 * @author : niu niu
 * @version : 1.0.0
 * @date : 2022/10/30 9:31
 */

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

public class Solution {
    //拆分子问题，只要有一个 子树 不是 平衡二叉树，则该树不是平衡二叉树
    //求高度
    private int heightOf(TreeNode root){
        //特殊情况判断
        if (root==null){
            return -1; // 0 也可以
        }
        //常规处理： 求他的左右子树高度
        int left = heightOf(root.left);
        int right = heightOf(root.right);
        //返回上层递归需要 加上本层的高度
        return Math.max(left,right)+1;
    }
    //求问题
    public boolean isBalanced(TreeNode root) {
        //特殊情况处理
        if (root == null){
            return true;
        }
        //常规处理： 判断他的左右子树是否平衡
        if (!isBalanced(root.left)){
            return false;
        }
        if (!isBalanced(root.right)){
            return false;
        }
        //核心处理方法， 求高度差，判断是否平衡
        int left = heightOf(root.left);
        int right = heightOf(root.right);
        int d= left-right;
        if (d<-1||d>1){
            // 不平衡退出口
            return false;
        }
        //平衡退出口
        return true;
    }
}
